package leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cino
 * justCode
 */
public class leetcode94 {

    @Test
    public void test() {
        TreeNode treeNode = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
        List<Integer> integers = inorderTraversal(treeNode);
        System.out.println();

    }

    public List<Integer> inorderTraversal(TreeNode root) {
        // 定义一个返回对象
        List<Integer> vals = new ArrayList<>();
        if (root == null){
            return vals;
        }
        // 进行递归获取遍历顺序的数据
        nextNode(root, vals);
        return vals;
    }

    //前中后序遍历 就是 中间这三步的顺序不同而已
    public void nextNode(TreeNode root,List<Integer> vals) {

        // -1、判断是不是有左节点，有的话对继续进行递归
        if (root.left != null){
            nextNode(root.left,vals);
        }
        // - 2、没有左节点，直接获取中间的值
        vals.add(root.val);
        // - 3、判断是不是有右节点，有的话对继续进行递归
        if (root.right != null){
            nextNode(root.right,vals);
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
